using System;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0019. 删除链表的倒数第N个节点")]
    public class No0019_RemoveNthFromEnd : AbsBaseTestItem
    {
        public class ListNode
        {
            public readonly int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }

        /*
        给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
        说明：
            给定的 n 保证是有效的。
        进阶：
            你能尝试使用一趟扫描实现吗？
        */

        public override void OnTest()
        {
            bool FuncEquals(ListNode n1, ListNode n2) => n1.ToJSONString() == n2.ToJSONString();

            string n1 = new ListNode(1)
            {
                next = new ListNode(2)
                {
                    next = new ListNode(3)
                    {
                        next = new ListNode(4)
                        {
                            next = new ListNode(5),
                        },
                    },
                },
            }.ToJSONString();
            string n2 = new ListNode(1)
            {
                next = new ListNode(2)
                {
                    next = new ListNode(3)
                    {
                        next = new ListNode(5),
                    },
                },
            }.ToJSONString();

            Assert.TestExe(RemoveNthFromEnd,
                n1.ToObject<ListNode>(), 2,
                equalsMethod: FuncEquals,
                n2.ToObject<ListNode>());

            Assert.TestExe(RemoveNthFromEnd2,
                n1.ToObject<ListNode>(), 2,
                equalsMethod: FuncEquals,
                n2.ToObject<ListNode>());
        }

        /// <summary>
        ///  方法一：两次遍历算法
        /// </summary>
        public ListNode RemoveNthFromEnd(ListNode head, int n)
        {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            int length = 0;
            ListNode first = head;
            while (first != null)
            {
                length++;
                first = first.next;
            }
            length -= n;
            first = dummy;
            while (length > 0)
            {
                length--;
                first = first.next;
            }
            first.next = first.next.next;
            return dummy.next;
        }

        /// <summary>
        ///  方法二：一次遍历算法
        /// </summary>
        public ListNode RemoveNthFromEnd2(ListNode head, int n)
        {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode first = dummy;
            ListNode second = dummy;
            // Advances first pointer so that the gap between first and second is n nodes apart
            for (int i = 1; i <= n + 1; i++)
            {
                first = first.next;
            }
            // Move first to the end, maintaining the gap
            while (first != null)
            {
                first = first.next;
                second = second.next;
            }
            second.next = second.next.next;
            return dummy.next;
        }
    }
}
